// 节点类
class Node {
	constructor(key) {
		this.key = key
		this.left = null
		this.right = null
	}
}
// 二叉搜搜树
class BinarySearchTree {
	constructor(key) {
		this.root = null
	}
	insert(key) {
		const newNode = new Node(key)
		if (this.root === null) {
			this.root = newNode
		} else {
			inserNodeByKey(newNode, this.root)
		}
	}
	search(key) {
		if (this.root === null) {
			return false
		}
		// let node = this.root
		// 方法一 ： 循环查找
		// while (node) {
		// 	if (key < node.key) {
		// 		node = node.left
		// 	} else if (key > node.key) {
		// 		node = node.right
		// 	} else {
		// 		return true
		// 	}
		// }
		// return false

		// 方法二 ： 递归查找
		return isFindNodeByKey(key, this.root)
	}
	// 先序遍历  中 左 右
	preOrderTraverse() {
		if (this.root === null) return null
		handelLeftOrRight(this.root, handelNode, 1)
	}
	// 中序遍历 左 中 右
	inOrderTraverse() {
		if (this.root === null) return null
		handelLeftOrRight(this.root, handelNode, 2)
	}
	// 后序遍历   左 右 中
	postOrderTraverserch() {
		if (this.root === null) return null
		handelLeftOrRight(this.root, handelNode, 3)
	}
	//层序遍历
	leveltraversal(hadel) {
		if (this.root === null) return false
		let queue = new Queue()
		queue.enquene(this.root)
		while (!queue.isEnpty()) {
			let node = queue.dequene()
			if (node.left) {
				queue.enquene(node.left)
			}
			if (node.right) {
				queue.enquene(node.right)
			}
			hadel(node.key)
		}
	}
	min() {
		if (this.root === null) return null
		let compareNode = this.root
		while (compareNode.left != null) {
			compareNode = compareNode.left
		}
		return compareNode.key
	}
	max() {
		if (this.root === null) return null
		let compareNode = this.root
		while (compareNode.right != null) {
			compareNode = compareNode.right
		}
		return compareNode.key
	}
	/**
	 * 第一种 删除的是叶子节点 直接删除
	 * 第二种 删除的节点有一个子节点 找到要删除节点的父节点指向要删除节点的子节点
	 * 第三种 复杂
	 * @param {*} key
	 */
	remove(key) {
		if (this.root === null) return false
		let res = getParentNodeByKey(key, this.root)
		const [parentNode, delNode, isPreantNodeLeftChild] = res
		if (res) {
			// 第一种 删除的是叶子节点
			if (delNode.left == null && delNode.right === null) {
				// 删除的是最根节点 最根节点是个叶子节点
				if (delNode === this.root) {
					this.root === null
				} else {
					if (isPreantNodeLeftChild) {
						parentNode.left = null
					} else {
						delNode.right = null
					}
				}
			}
			// 第二种 删除的节点只存在一个子节点且是左节点
			else if (delNode.right === null) {
				// 特殊情况 删除节点为根节点 根节点只有一个左节点
				if (delNode === this.root) {
					this.root = delNode.left
				} else if (isPreantNodeLeftChild) {
					parentNode.left = delNode.left
				} else {
					parentNode.right = delNode.left
				}
			}
			// 第二种 删除的节点只存在一个子节点且是右节点
			else if (delNode.left === null) {
				// 特殊情况 删除节点为根节点 根节点只有一个右节点
				if (delNode === this.root) {
					this.root == delNode.right
				} else if (parentNode.right === null) {
					if (isPreantNodeLeftChild) {
						parentNode.left = delNode.left
					} else {
						parentNode.right = delNode.right
					}
				}
			}
			// 第三种要删除节点存在两个子节点
			else {
				let successer = getSuccessor(delNode)
				console.log(successer)
				if (delNode === this.root) {
					this.root = successer
				} else if (isPreantNodeLeftChild) {
					parentNode.left = successer
				} else {
					parentNode.right = successer
				}
				successer.left = delNode.left
			}
			return true
		} else {
			return false
		}
	}
}
// 插入工具类 插入节点
function inserNodeByKey(newNode, compareNode) {
	if (newNode.key < compareNode.key) {
		// 左遍历
		if (compareNode.left === null) {
			compareNode.left = newNode
			return
		}
		inserNodeByKey(newNode, compareNode.left)
	} else {
		// 右遍历
		if (compareNode.right === null) {
			compareNode.right = newNode
			return
		}
		inserNodeByKey(newNode, compareNode.right)
	}
}
// 查询工具类 根据 key 找节点
function isFindNodeByKey(key, compareNode) {
	if (compareNode === null) {
		return false
	}
	if (key < compareNode.key) {
		return isFindNodeByKey(key, compareNode.left)
	} else if (key > compareNode.key) {
		return isFindNodeByKey(key, compareNode.right)
	} else {
		return true
	}
}
//  遍历工具类 根据 key 找左/右子树 type=1 为先序  2中序 3后序
function handelLeftOrRight(node, handelNode, type) {
	if (type === 1) {
		if (node !== null) {
			// 处理经过的节点
			handelNode(node.key)
			// 处理经过节点的左子节点
			handelLeftOrRight(node.left, handelNode, type)
			// 处理经过节点的右子节点
			handelLeftOrRight(node.right, handelNode, type)
		}
	} else if (type === 2) {
		if (node !== null) {
			// 处理经过节点的左子节点
			handelLeftOrRight(node.left, handelNode, type)
			// 处理经过的节点
			handelNode(node.key)
			// 处理经过节点的右子节点
			handelLeftOrRight(node.right, handelNode, type)
		}
	} else if (type === 3) {
		if (node !== null) {
			// 处理经过节点的左子节点
			handelLeftOrRight(node.left, handelNode, type)
			// 处理经过节点的右子节点
			handelLeftOrRight(node.right, handelNode, type)
			// 处理经过的节点
			handelNode(node.key)
		}
	}
}
// 遍历工具类 输出
function handelNode(key) {
	console.log(key)
}
// 删除工具类 根据 key 找到父节点
function getParentNodeByKey(key, node) {
	let parentNode = null // 删除节点的父节点
	let isPreantNodeLeftChild = true // 1 为左边 0为右边
	while (node) {
		if (key < node.key) {
			parentNode = node
			isPreantNodeLeftChild = true
			node = node.left
		} else if (key > node.key) {
			parentNode = node
			isPreantNodeLeftChild = false
			node = node.right
		} else {
			return [parentNode, node, isPreantNodeLeftChild]
		}
	}
	return null
}
// 删除工具类 左子树的最大值  右子树的最小值
function getSuccessor(delNode) {
	let successerParentNode = delNode
	let successer = delNode
	let currentNode = delNode.right
	while (currentNode !== null) {
		successerParentNode = successer
		successer = currentNode
		currentNode = currentNode.left
	}
	// 找到的后继节点不是是删除节点的右节点
	if (successer != delNode.right) {
		successerParentNode.left = successer.right
		successer.right = delNode.right
	}
	return successer
}

// 队列
class Queue {
	constructor() {
		this.items = []
	}
	enquene(val) {
		this.items.push(val)
	}
	dequene() {
		return this.items.shift()
	}
	front() {
		return this.items[0]
	}
	isEnpty() {
		return this.items.length === 0
	}
	size() {
		return this.items.length
	}
	toString() {
		return this.items.join('').replace(/,/, '')
	}
}
